# !/usr/usuari/des python
#  -*- coding: utf-8 -*-
"""
@Author        : itgnay
@Time          : 2022/12/19 19:16
@FileName      : 动态规划算法.py
@LastEditors   : None
@Editors       : PyCharm
"""
import numpy as np

moneys = [1, 5, 10, 20, 50, 100]
num = 150
nums = np.zeros((num + 1, 1))
# 初始化
for i in moneys:
    if i <= len(nums):
        nums[i] = 1
# 动态循环
for i in range(2, len(nums)):
    k = i  # 最优解
    for j in range(i, int(i / 2) - 1, -1):
        if (nums[i - j] > 0 or i == j) and nums[j] > 0:
            _k = nums[i - j] + nums[j]
            if k > _k:
                k = _k
    nums[i] = k
print(nums)
